#ifndef HEAD_H
#define HEAD_H
#include<iostream>
using namespace std;

struct node{
    int key;
    node *leftC=NULL;
    node *rightC=NULL;
    node *pre=NULL;
    int leftTag,rightTag;
};

template<class T>
class BinarySearchTree{
private:
    node*root=NULL;
public:
    BinarySearchTree();
    ~BinarySearchTree();
    T addNode(T num);

    node*findNode(int num,node* current);
    bool search(int num);

    void deleteNodes(node* current);

    void deleteSingleNode(int num);

    void show();
    void showInPre(node* current);
};



template<class T>
BinarySearchTree<T>::BinarySearchTree(){
}
template<class T>
void BinarySearchTree<T>::deleteNodes(node *current){
    if(current!=NULL){
        deleteNodes(current->leftC);
        deleteNodes(current->rightC);
        delete current;
    }
}

template<class T>
BinarySearchTree<T>::~BinarySearchTree(){
    deleteNodes(root);
}

template<class T>
void BinarySearchTree<T>::show(){
    cout<<endl;
    showInPre(root);
}
template<class T>
void BinarySearchTree<T>::showInPre(node *current){
    if(current!=NULL){
        cout<<current->key<<"\t";
        showInPre(current->leftC);
        showInPre(current->rightC);
    }
}
template<class T>
T BinarySearchTree<T>::addNode(T num){
    node*p=root,*previous=NULL;
    while(p!=NULL){
        previous=p;
        if(p->key<num){
            p=p->rightC;
        }
        else
            p=p->leftC;
    }
    if(root==NULL){
        root=new node;
        root->key=num;
    }
    else if(previous->key<num){
        previous->rightC=new node;
        previous->key=num;
    }
    else{
        previous->leftC=new node;
        previous->key=num;
    }
}

template<class T>
node* BinarySearchTree<T>::findNode(int num,node* current){
    while((root!=NULL)&&(num!=current->key))
        current=(num<current->key?findNode(num,current->leftC):findNode(num,current->rightC));
    return current;
}
template<class T>
bool BinarySearchTree<T>::search(int num){
   if( findNode(num,root))
       return true;
   else
       return false;
}


template<class T>
void BinarySearchTree<T>::deleteSingleNode(int num){
    node *tarNode=findNode(num,root);
    node *current=tarNode;
    if(tarNode!=NULL){
        if(!tarNode->rightC)
            tarNode=tarNode->leftC;
        if(!tarNode->leftC)
            tarNode=tarNode->rightC;
        else{
            current=tarNode->leftC;
            while(current->rightC!=NULL)
                current=current->rightC;
            current->rightC=tarNode->rightC;
            current=tarNode;
            tarNode=tarNode->leftC;
        }
        delete current;
    }
}

#endif // HEAD_H
